package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/4/27 9:07
 */
public class C938 {

    public static int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int lv = rangeSumBST(root.left, low, high);
        int v = root.val >= low && root.val <= high ? root.val : 0;
        int rv = rangeSumBST(root.right, low, high);
        return lv + rv + v;
    }


    public static int rangeSumBST2(TreeNode root, int low, int high) {
        if (root == null) return 0;
        int v = 0;
        if (root.val >= low && root.val <= high) {   // 在范围内, 来一次中续操作
            v += rangeSumBST(root.left, low, high) + root.val + rangeSumBST(root.right, low, high);
        } else if (root.val < low) {  // 当前节点比最小值小, 去右边查询
            v += rangeSumBST(root.right, low, high);
        } else {    // 必当钱最大值要大
            v += rangeSumBST(root.left, low, high);
        }
        return v;
    }

    public static void main(String[] args) {
        Integer[] arr = {
                18, 9, 27, 6, 15, 24, 30, 3, null, 12, null, 21
        };
        TreeNode root = TreeUtil.generateTreeByArr(arr);
        int low = 18, high = 24;
        System.out.println(rangeSumBST(root, low, high));
        System.out.println(rangeSumBST2(root, low, high));
    }

}
